using System;

namespace ApiScanner.Core
{
	/// <summary>
	/// Summary description for BoyerMoore.
	/// </summary>
	//
	// Classic Boyer-Moore algorithm
	// Reference: http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140
	//
	public class FastByteSearcher
	{
		protected int[] suffixes = null;
		protected int[] goodsuffix = null;

		protected byte[] _ContentBuffer; //text
		protected byte[] _Pattern; //pattern
		protected int _PatternSize;
		protected int _ContentSize;
		protected int _Index;
		protected int[] _BadChars;
		protected bool[] _BadCharSet;

		public FastByteSearcher(byte[] contentBuffer, byte[] pattern, int contentLength): this(contentBuffer, pattern, 0, contentLength) {}

		public FastByteSearcher(byte[] contentBuffer, byte[] pattern): this(contentBuffer, pattern, contentBuffer.Length, 0) {}

		public FastByteSearcher(byte[] contentBuffer, byte[] pattern, int contentOffset, int contentLength) 
		{
			_ContentBuffer = contentBuffer;
			_ContentSize = contentOffset + contentLength;
			_Pattern = pattern;
			_PatternSize = pattern.Length;

			InitBadChar();
			InitGoodSuffix();
			_Index = contentOffset;
		}

		public int FindNext()
		{
			int result = -1;
			while( _Index <= _ContentSize -_PatternSize)
			{
				int i;
				for( i = _PatternSize-1; (i >= 0) && (_Pattern[i] == _ContentBuffer[_Index + i]);--i); //compare patern with text at index

				if( i < 0 ) // we found a match!
				{
					result = _Index;
					_Index += goodsuffix[0];
					return result;
				}
				else
				{
					if (!_BadCharSet[_ContentBuffer[_Index + i]])
						// char not in pattern. we can align new test pattern immediately after the char.
						_Index += 1+i;
					else
					{
						int gs = goodsuffix[i]; // maximum shifting according to the GoodSuffix heuristic
						int bc = i - _BadChars[_ContentBuffer[_Index + i]]; // maximum shifting according to the BadChar heuristic
						_Index += Math.Max(gs,bc); // use the best heuristic.
					}
				}
			}
			return result;
		}

		private void InitBadChar()
		{
			_BadCharSet = new bool[256];
			_BadChars = new int[256];
			// badchar[x] will correspond to the position of the rightmost occurrence of x.
			for(int i = 0; i < _PatternSize; i++)
			{
				_BadCharSet[_Pattern[i]] = true;
				_BadChars[_Pattern[i]] = i;
			}
		}

		private void InitSuffixes()
		{
			suffixes = new int[_PatternSize];
			int f,g;
			f = 0;
			g = _PatternSize;
			for(int i = _PatternSize -2; i >= 0; --i)
			{
				if(i > g &&	suffixes[_PatternSize-1 + i-f] < i - g)
					suffixes[i] = suffixes[_PatternSize-1 + i-f];
				else
				{
					f = i;
					if(i < g) g = i;
					while(g >= 0 && _Pattern[g] == _Pattern[_PatternSize-1 + g-f]) --g;
					suffixes[i] = f-g;
				}
			}
		}

		private void InitGoodSuffix()
		{
			int i, j;
			InitSuffixes();

			goodsuffix = new int[_PatternSize];

			for(i = 0; i < _PatternSize; ++i)
				goodsuffix[i] = _PatternSize;
			j = 0;
			for(i = _PatternSize-1; i >= -1; --i)
			{
				if(i == -1 || suffixes[i] == i+1)
					while(j < _PatternSize-1 -i)
					{
						if(goodsuffix[j] == _PatternSize)
							goodsuffix[j] = _PatternSize-1 -i;
						++j;
					}
			}
			for(i = 0; i < _PatternSize -1; ++i)
				goodsuffix[_PatternSize-1 - suffixes[i]] = _PatternSize-1 -i;
		}
	}
}
